package leetCode.cdj;

import com.alibaba.fastjson.JSON;

public class aa {
	
	public static void main(String[] args) {
		int[] arr = new int[] {5,4,8,3,2,5,1,5,6,2,54,111,111,222,2,6,5,54,5,5,6,854,9684,698,46,54,654,65,4,999999,65,46,54,654,654,65,6,5,6,5,522,52,655,5,5,2,6,8,6,63,56,5,6,6,6,2,6,89,2,69,5,3,6958,6,96,6,9,6,6,9,6,69,6,1,2,2,1};
		System.out.println(JSON.toJSONString(maxSubsequence(arr, 9)));
		System.out.println(JSON.toJSONString(maxSubsequence1(arr, 9)));
	}

	public static int[] maxSubsequence(int[] nums, int k) {
		int [] result = new int[k];
		// length of nums
		int n = nums.length;
		// need to delete
		int remain = n - k;
		// nums of result 
		int top = -1;
		for(int num : nums) {
			while(top>=0 && remain>0 && result[top]<num) {
				top--;
				remain--;
			}
			if(top<k-1) {
				result[++top] = num;
			}else {
				remain--;
			}
		}
		return result;
    }
	
	public static int[] maxSubsequence1(int[] nums, int k) {
        int length = nums.length;
        int[] stack = new int[k];
        int top = -1;
        int remain = length - k;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (top >= 0 && stack[top] < num && remain > 0) {
                top--;
                remain--;
            }
            if (top < k - 1) {
                stack[++top] = num;
            } else {
                remain--;
            }
        }
        return stack;
    }

}
